package com.cty.fourthDay;

import java.util.Arrays;

/*
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作
 * */
public class Q_4 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 0, 3, 12};
        moveZeroes2(nums);
        System.out.println(Arrays.toString(nums));
    }

    //自己的思路 事件复杂度（n^2） 不好 暴力方法
    public static void moveZeroes(int[] nums) {
        if (nums == null || nums.length == 0) return;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                int k = i + 1;
                while (k < nums.length && nums[k] == 0) {
                    k++;
                }
                if (k != nums.length) {
                    nums[i] = nums[k];
                    nums[k] = 0;
                }
            }
        }
    }

    //官方的题解 时间复杂度(n)
    public static void moveZeroes2(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int n = nums.length, left = 0, right = 0;

        while (right < n) {
            if (nums[right] != 0) {
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
            right++;
        }
    }

}
